#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <list>
#include <string>
#include <map>
#include <utility>


#include <iostream>
#include <sys/time.h>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <cmath>
#include <unistd.h>

using std::vector;
using std::unordered_map;
using std::map;
using std::set;
using std::string;
using std::list;
using std::cout;
using std::endl;
using std::pair;
using std::make_pair;
using std::istream;
using std::ostream;

// Leetcode 146 LURCache的实现

// https://leetcode-cn.com/problems/lru-cache/

// 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
// 实现 LRUCache 类：
// LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
// int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
// void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
// 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

// 示例：

// 输入
// ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
// [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
// 输出
// [null, null, null, 1, null, -1, null, -1, 3, 4]

// 解释
// LRUCache lRUCache = new LRUCache(2);
// lRUCache.put(1, 1); // 缓存是 {1=1}
// lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
// lRUCache.get(1); // 返回 1
// lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
// lRUCache.get(2); // 返回 -1 (未找到)
// lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
// lRUCache.get(1); // 返回 -1 (未找到)
// lRUCache.get(3); // 返回 3
// lRUCache.get(4); // 返回 4


// 提示：

// 1 <= capacity <= 3000
// 0 <= key <= 10000
// 0 <= value <= 105
// 最多调用 2 * 105 次 get 和 put

// struct cc
// {

// }



class LRUCache
{
public:
    LRUCache(int capacity);
    int get(int key);
    void put(int key, int value);
    void print()const{
        for(auto& elem : _time){
            cout << elem.first << "  " << elem.second << endl;
        }
    }

private:
    unordered_map<int, pair<int, __syscall_slong_t>> _cache;
    map<__syscall_slong_t, int> _time;
    int _size;
    int _capacity;
};

LRUCache::LRUCache(int capacity)
    : _size(0)
    , _capacity(capacity){}

int LRUCache::get(int key)
{
    struct timespec tn;
    clock_gettime(CLOCK_REALTIME, &tn);

    auto it = _cache.find(key);
    if(it == _cache.end()){return -1;}

    _time.erase(it->second.second);
    _time.insert({tn.tv_nsec, key});
    it->second.second = tn.tv_nsec;

    return it->second.first;
}

void LRUCache::put(int key, int value){
    struct timespec tn;
    clock_gettime(CLOCK_REALTIME, &tn);
    auto it = _cache.insert({key, {value, tn.tv_nsec}});
    if(it.second == false){
        it.first->second.first = value;

        _time.erase(it.first->second.second);
        it.first->second.second = tn.tv_nsec;
        _time.insert({tn.tv_nsec, key});
        

    }else{
        _time.insert({tn.tv_nsec, key});
        auto ret = _cache.find(key);
        if(_size < _capacity){++_size;}
        else if(_size == _capacity){
            auto tmp = _time.begin();
            _cache.erase(tmp->second);
            _time.erase(tmp);
        }
    }
}


int main()
{
    LRUCache lRUCache(2);
    lRUCache.put(1, 11); // 缓存是 {1=1}
    lRUCache.put(2, 22); // 缓存是 {1=1, 2=2}
    cout << lRUCache.get(1) << endl;    // 返回 1
    lRUCache.put(3, 33); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
    cout << lRUCache.get(2) << endl;    // 返回 -1 (未找到)
    lRUCache.put(4, 44); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
    cout << lRUCache.get(1) << endl;    // 返回 -1 (未找到)
    cout << lRUCache.get(3) << endl;    // 返回 3
    cout << lRUCache.get(4) << endl;    // 返回 4
    return 0;
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */


